The present invention generally relates to allocating access across a shared communications medium and, in particular, to allocating bandwidth used to convey data of competing users across a shared communications medium of a Carrier Network.
As used herein, a xe2x80x9cCarrier Networkxe2x80x9d generally refers to a computer network through which users (such as homes and businesses) communicate with various service providers. The Carrier Network extends from the location of each user to an intermediate switched/routed network (hereinafter xe2x80x9cIntermediate Networkxe2x80x9d). The service providers, in turn, are connected to the Intermediate Network, either directly or indirectly via the Internet, for communications with the users. The Carrier Network is maintained by a xe2x80x9cCarrier,xe2x80x9d which also may serve as a service provider for certain services. For example, a Carrier or a related entity may serve as an Internet service provider (ISP).
Two prevalent types of Carrier Networks include a xe2x80x9cShared Access Carrier Network,xe2x80x9d in which data of multiple users are conveyed together over a shared communications medium between the users and the Intermediate Network, and a xe2x80x9cDedicated Connection Carrier Network,xe2x80x9d in which data of each user are conveyed alone between the user and the Intermediate Network and are not combined with data of other users. One of the most prevalent Shared Access Carrier Networks today is found in the Data-Over-Cable (DOC) Network, which includes the traditional network constructed from coaxial cable and the hybrid fiber coaxial (HFC) network constructed with both fiber optical cabling and coaxial cable. Other Shared Access Carrier Networks include wireless and digital subscriber line (xDSL) networks (the xDSL lines typically being aggregated onto an oversubscribed backhaul trunk into the Intermediate Network, with the trunk defining the shared communications medium).
For example, with regard to DOC Networks, and with reference to FIG. 1 wherein a conventional DOC Network 40 is illustrated, data packets are transmitted in a downstream direction from a cable modem termination system (CMTS) 30, which is located in a headend 36 (or distribution hub) of a Carrier, over a coaxial cable 32 to respective cable modems (CMs) 34 of users. All of the CMs 34 are attached by the coaxial cable 32 to the CMTS 30 in an inverted tree configuration, and each CM 34 connected to the coaxial cable 32 listens to all broadcasts from the CMTS 30 transmitted through the coaxial cable 32 for data packets addressed to it, and ignores all other data packets addressed to other CMs 34. Theoretically, a CM 34 is capable of receiving data in the downstream direction over a 6 MHz channel with a maximum connection speed of 30-40 Mbps. Data packets also are transmitted in the upstream direction over a 2 MHz channel by the CMs 34 to the CMTS 30 typically using time division multiplexing (TDM) and at a maximum connection speed of 1.5-10 Mbps.
The headend 36 in the DOC Network 40 includes a plurality of CMTSs, with each CMTS supporting multiple groups of CMs each connected together by a respective coaxial cable. Each such group of CMs connected to a CMTS defines a Shared Access Carrier Network, with the coaxial cable in each representing the shared communications medium. This arrangement of a group of CMs connected to a CMTS by a coaxial cable is referred to herein as a xe2x80x9cCable Network.xe2x80x9d Accordingly, the DOC Network 40 includes a plurality of Cable Networks 38 originating from CMTSs at the headend 36 of the Carrier, with a particular Cable Network 38 being illustrated in an expanded view in FIG. 1. The DOC Network 40 also includes multiple headends 36,64,66.
In contrast to the Shared Access Carrier Network, a user in the Dedicated Connection Carrier Network establishes a dedicated connection directly with the Intermediate Network for the transfer of data directly therebetween, and no data of other users travel over the dedicated connection. Examples of a dedicated connection are shown for comparison in FIG. 1 and include a connection established by a telephony modem 74 and a connection established by an ISDN modem 76. Both downstream and upstream connection speeds in a Dedicated Connection Carrier Network range from a maximum of 53 kbps in a telephony modem connection to a maximum of 128 kbps in a basic rate interface ISDN connection.
Connection speeds and, more importantly, throughput ratexe2x80x94the amount of data actually transmitted successfully in a given time intervalxe2x80x94are important in minimizing downtime that users spend waiting for HTML documents to download from the Web. A Shared Access Carrier Network is considered superior to a comparable Dedicated Connection Carrier Network because the maximum instantaneous connection speed offered by the Shared Access Carrier Network is greater. A Shared Access Carrier Network is considered xe2x80x9ccomparablexe2x80x9d to a Dedicated Connection Carrier Network where the entire bandwidth over a shared communications medium of the Shared Access Carrier Network equals an aggregate bandwidth that is divided between and dedicated to users in a Dedicated Connection Carrier Network. Accordingly, Shared Access Carrier Networks are able to offer significantly faster downloads of web documents, emails, and file transfers that are not considered available in Dedicated Connection Carrier Networks.
Furthermore, new multimedia applications and Internet services, such as voice and video communications via the Internet, now are offered which require even greater throughput rates for acceptable levels of service than that of the traditional Internet services, i.e., throughput rates greater than that required for acceptable text-based Web browsing, file transferring, and email communication. It is believed that these new multimedia applications and Internet services cannot adequately be provided for over Dedicated Connection Carrier Networks and that, consequently, Shared Access Carrier Networks ultimately will prevail as the predominant type of Carrier Network for Internet access by users.
As Shared Access Carrier Networks emerge as the favored type of network, it is believed that open access to such networks by different competing service providers will become an important commercial and legislative issue. Moreover, as more and more service providers seek to provide users with services over Shared Access Carrier Networks, it is believed that users of such service providers will receive inadequate bandwidth over the Shared Access Carrier Networks to meet minimum standards of quality, especially in Cable Networks where bandwidth is provided on a best efforts basis.
Accordingly, it is believed that a need exists for a method by which a service provider competing for users of a shared communications medium can seek protection against bandwidth starvation of the users of the shared communications medium that are its customers. Conversely, it is also believed that a need exists for a method that will accommodate differing demands for network access by users competing for such access across the shared communications medium.
Briefly summarized, the present invention relates to a method of providing network access across a shared communications medium between competing users. In particular, the present invention includes the steps of allocating network access to at least two xe2x80x9cuser classesxe2x80x9d for a first future time interval and, for each user class, allocating network access to each user within the class for the first time interval. The present invention further includes the additional step of allocating network access to each user class for a second future time interval succeeding the first time interval and, for each user class, allocating network access to each user for the second time interval. Each user receives a first determined allowance of network access for utilization during the first time interval equal to that user""s allocation for the first time interval, and a second determined allowance of network access for utilization during the second time interval equal to that user""s allocation for the second time interval. The user allocationsxe2x80x94and hence the user allowancesxe2x80x94preferably differ as between the first and second time intervals.
As used herein, a xe2x80x9cbandwidth allowancexe2x80x9d represents a respective maximum level of network access that will be made available to a user class or to a user during a particular time interval, and does not necessarily represent the level of network access that will be utilized by the user class or user during such time interval.
As used herein, a xe2x80x9cuser classxe2x80x9d is intended to refer to a grouping of users who compete for access across a shared communications medium and who have some characteristic in common. The characteristic may, for example, be that the users are customers who receive Internet service over the shared communications medium from the same service provider. The characteristic also may, for example, be that the users each subscribe to receive a particular level of network access across the shared communications medium, or that the users receive the same level of a particular service that is provided across the shared communications medium. Furthermore, a user class is a grouping of users to which, collectively, a determined amount of bandwidth is allocated as opposed to other user classes. In this regard, users that are not classified are considered to be part of a default user class having in common that fact that no other classification applies to them. Accordingly, all users of a shared communications network can be classified.
In features of the present invention, the method includes the steps of monitoring network access usage by the users, and forecasting network access usage of each user in a future time interval. Another feature includes the step of prioritizing the users for the allocation of network access.
One of many preferred embodiments of the present invention includes the monitoring of bandwidth consumption of each user across the shared communications medium of a Cable Network and tracking the collective bandwidth consumption of each user class; based on the monitored bandwidth consumptions, the forecasting of bandwidth consumption of each user in a future time interval and the calculation based thereon of the collective bandwidth consumption of each user class; the prioritization of users and the prioritization of user classes; and the subsequent allocation of bandwidth to each user class, and then to each user, in decreasing order of priority for determining bandwidth allowances during the future time interval. Users and user classes are prioritized based on one or more various prioritization policies, including fairness considerations such as individual or collective user throughput during a particular time interval, individual or collective user data loss for a particular time interval, individual or collective user bandwidth consumption for a particular time-of-day, an established minimum quality of service (QoS) standard, or combination thereof. Other prioritization policies include the prioritization of users and user classes based upon provisions found in each user""s respective service level agreement (SLA) or provisions found in each class"" service level agreement (CSLA), and the prioritization of users based upon each user""s forecasted bandwidth consumption for the future time interval and the prioritization of user classes based upon each class"" collective forecasted bandwidth consumption. In alternative embodiments, the bandwidth that is requested, rather than the bandwidth that is consumed, is monitored and forecasted.
Further features and benefits of the present invention will be apparent from a detailed description of preferred embodiments thereof taken in conjunction with the following drawings, wherein like elements are referred to with like reference numbers, and wherein:
FIG. 1 illustrates a conventional DOC Network;
FIG. 2 illustrates a first DOC Network of the present invention;
FIG. 3 illustrates a second DOC Network of the present invention;
FIG. 4 illustrates a third DOC Network of the present invention;
FIG. 5 illustrates a fourth DOC Network of the present invention;
FIG. 6 illustrates a system architecture of software components that perform preferred methods of the present invention in the DOC Networks of FIGS. 2-5;
FIG. 7 illustrates a flowchart of the steps of a preferred routine for forecasting bandwidth of each user for a future time interval;
FIG. 8 illustrates a flowchart of the steps of generating a forecasted bandwidth for a user in accordance with the ARRSES Function of the preferred routine of FIG. 7;
FIG. 9 illustrates a flowchart of the steps of generating a forecasted bandwidth for a user in accordance with the HW Function of the preferred routine of FIG. 7;
FIG. 10 illustrates a graph of user throughput rates versus user data loss rates for two users relative to a target minimum QoS standard;
FIG. 11 illustrates a flowchart of a first preferred method of prioritizing classes and allocating collective bandwidth to each class;
FIG. 12 illustrates a flowchart of a second preferred method of prioritizing classes and allocating collective bandwidth to each class;
FIG. 13 illustrates a flowchart of a third preferred method of prioritizing classes and allocating collective bandwidth to each class;
FIG. 14 illustrates a flowchart of a fourth preferred method of prioritizing classes and allocating collective bandwidth to each class;
FIGS. 15a and 15b illustrate a flowchart of a fifth preferred method of prioritizing classes and allocating collective bandwidth to each class;
FIGS. 16a and 16b illustrate a flowchart of a sixth preferred method of prioritizing classes and allocating collective bandwidth to each class;
FIG. 17 illustrates a flowchart of a first preferred method of prioritizing users and allocating bandwidth to each user within a class;
FIG. 18 illustrates a flowchart of a second preferred method of prioritizing users and allocating bandwidth within a class;
FIG. 19 illustrates a flowchart of a third preferred method of prioritizing users and allocating bandwidth within a class;
FIG. 20 illustrates a flowchart of a fourth preferred method of prioritizing users and allocating bandwidth within a class;
FIGS. 21a and 21b illustrate a flowchart of a fifth preferred method of prioritizing users and allocating bandwidth within a class;
FIGS. 22a and 22b illustrate a flowchart of a sixth preferred method of prioritizing users and allocating bandwidth within a class;
FIG. 23 illustrates a flowchart of a preferred method of updating a DOC Network for a DOCSIS 1.0 compliant Cable Network;
FIG. 24 illustrates the allocation of bandwidth to users within a class during a first time interval;
FIG. 25 illustrates the allocation of bandwidth to the users of FIG. 24 during a second time interval; and
FIG. 26 illustrates a flowchart of a preferred method of soliciting a user to modify the user""s SLA based on monitored network access usage of the user.